// common.c
// functions that are common to two or more of the knapsack solution methods: enum,
// branch-and-bound, dynamic programming and greedy

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


extern FILE *fp;
extern int N;
extern int C;
extern int *w;
extern int *v;
extern int *kindex;  // a list of indexes (we can sort these instead of moving the items)
extern int QUIET;


void read_knapsack_instance(char *filename);
void print_instance();
void sort_by_ratio();
int print_sol2(int *s,  int *tv, int *tw);
static int mycomp(const void *a, const void *b);

void read_knapsack_instance(char *filename)
{
  int i;
  if((fp=fopen(filename,"rb")))
    {
      fscanf(fp,"%d\n", &N);  // read the number of items
    

      if(!(w=(int *)malloc(N*sizeof(int))))
	{
	  fprintf(stderr,"Could not allocate memory for weights vector\n");
	  exit(1);
	}
      if(!(v=(int *)malloc(N*sizeof(int))))
	{
	  fprintf(stderr,"Could not allocate memory for values vector\n");
	  exit(1);
	}
      if(!(kindex=(int *)malloc(N*sizeof(int))))
	{
	  fprintf(stderr,"Could not allocate memory for index vector\n");
	  exit(1);
	}

      for(i=0;i<N;i++)
	fscanf(fp,"%d %d %d\n", &kindex[i], &v[i], &w[i]);

      fscanf(fp,"%d\n", &C);  // read the knapsack capacity
    }
  else
    {
      fprintf(stderr,"Could not open file %s. Exiting.\n", filename);
      exit(1);
    }
     
}

void print_instance()
{
  int i;
  printf("item\tW\tV\n");
  for(i=0;i<N;i++)
    printf("%d\t%d\t%d\n", kindex[i], w[i], v[i]);
  printf("%d\n", C);
}

void sort_by_ratio()
{
  int i;
  // sort the item indexes
  qsort(kindex, N, sizeof(int), &mycomp);

  // print out the sorted order as a check
  for(i=0;i<N;i++)
    printf("%d\t%d\t%f\n", w[kindex[i]-1], v[kindex[i]-1],  (double)v[kindex[i]-1]/(double)w[kindex[i]-1]);
}

static int mycomp(const void *a, const void *b)
{
  // compare value-to-weight ratios
  int ia,ib;
  ia=(*(int *)a)-1;
  ib=(*(int *)b)-1;
 
  if((double)v[ia]/(double)w[ia] > (double)v[ib]/(double)w[ib])
    return(-1);
  else if((double)v[ia]/(double)w[ia] < (double)v[ib]/(double)w[ib])
    return(1);
  else
    return(0);
      
}




int print_sol2(int *s, int *tv, int *tw)
{
  // The vector s is a binary vector of length N, describing the items to be put in the knapsack.
  // The (global) kindex array maps item i to kindex[i].
  // So s[i]=1 means item kindex[i] should be taken.
  // In order to print out item numbers referred to by s in ascending order, we need to reverse the kindex mapping.
  // This function does it.

  int i;
  *tv=0;
  *tw=0;
  int y[N]; // auxiliary binary array to do reverse-mapping


  // First pass: unmap the mapping using y[]
  for(i=0;i<N;i++)
    {
      if(s[i]==1)
	y[kindex[i]-1]=1;
      else
	y[kindex[i]-1]=0;
    }

  // Second pass: now print out item numbers of items to be packed in ascending order
  if(!(QUIET))
    printf("Pack items: ");
  for(i=0;i<N;i++)
    {
      if(y[i]==1)
	{
	  if(!(QUIET))
	    printf("%d ", i+1);
	  *tv+=v[i];
	  *tw+=w[i];
	}
    }

  // Finally, print out the value, weight and Capacity, and feasibility
  if(!(QUIET))
    {
      if(*tw>C)
	printf("\nvalue=%d weight=%d > Capacity=%d: Infeasible\n",*tv,*tw,C);
      else
	printf("\nvalue=%d weight=%d <= Capacity=%d: Feasible\n",*tv,*tw,C);
    }
  if(*tw>C)
    return 1;  // return 1 for infeasible solutions
  else
    return 0;
      
  
}
